package demo.DataStrucAndAlgo.Tree;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/31-07-31-12:01
 * @Description：demo.DataStrucAndAlgo.Tree  二叉树遍历查找
 */
/*
满二叉树：
    二叉树的所有叶子结点都在最后一层，且结点总数=2^n-1,n为层数
完全二叉树：
    如果该二叉树的所有叶子结点都在最后一层或者倒数第二层，
    而且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续
二叉树遍历：
    前序遍历：先输出父节点，再遍历左子树和右子树
    中序遍历：先遍历左子树，再输出父节点，再遍历右子树
    后序遍历：先遍历左子树和右子树，最后输出父节点
 */
class Node2{
    private int id;
    private String data;
    private Node2 left;
    private Node2 right;

    public Node2(int id, String data) {
        this.id = id;
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", data='" + data + '\'' +
                '}';
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Node2 getLeft() {
        return left;
    }

    public void setLeft(Node2 left) {
        this.left = left;
    }

    public Node2 getRight() {
        return right;
    }

    public void setRight(Node2 right) {
        this.right = right;
    }
    //前序遍历
    public Node2 preOrderSearch(int id){
        if(id == this.getId()){
            return this;
        }
        Node2 node = null;
        //System.out.println(this);
        if(this.left != null){
            node = this.left.preOrderSearch(id);
        }
        if(this.right != null){
            node = this.right.preOrderSearch(id);
        }
        return node;
    }

    //中序遍历
    public Node2 infixOrderSearch(int id){
        Node2 node = null;
        if(this.left != null){
            node = this.left.infixOrderSearch(id);
        }
        if(this.getId() == id){
            return this;
        }
        return node;
    }

    //后序遍历
    public Node2 postOrderSearch(int id){
        Node2 node = null;
        if(this.left != null){
            node = this.left.postOrderSearch(id);
        }
        if(this.right != null){
            node = this.right.postOrderSearch(id);
        }
        if(this.getId() == id){
            return this;
        }
        return node;
    }
}

class binTree{
    private Node2 root;     //根节点
    public Node2 getRoot() {
        return root;
    }
    public void setRoot(Node2 root) {
        this.root = root;
    }
    //前序遍历
    public void preOrderSearch(int id){
        if(root != null){
            System.out.println("查询结果为： " + root.preOrderSearch(id));
        }else{
            System.out.println("此二叉树为空！");
        }
    }
    //中序遍历
    public void infixOrderSearch(int id){
        if(root != null){
            System.out.println("查询结果为： " + root.infixOrderSearch(id));
        }else{
            System.out.println("此二叉树为空！");
        }
    }
    //后序遍历
    public void postOrderSearch(int id){
        if(root != null){
            System.out.println("查询结果为：" + root.postOrderSearch(id));
        }else{
            System.out.println("此二叉树为空！");
        }
    }
}

public class BinarySearchTree {
    public static void main(String[] args) {
        binTree tree=new binTree();
        Node2 node1=new Node2(1,"one");
        Node2 node2=new Node2(2,"two");
        Node2 node3=new Node2(3,"three");
        Node2 node4=new Node2(4,"four");
        Node2 node5=new Node2(5,"five");
        tree.setRoot(node1);
        tree.getRoot().setLeft(node2);
        tree.getRoot().setRight(node3);
        node3.setLeft(node4);
        node3.setRight(node5);

        System.out.println("前序查找");
        tree.preOrderSearch(5);

        System.out.println("中序查找");
        tree.infixOrderSearch(1);

        System.out.println("后序查找");
        tree.postOrderSearch(0);
    }
}
